//给出一个区间的集合，请合并所有重叠的区间。 
//
// 
//
// 示例 1: 
//
// 输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
//输出: [[1,6],[8,10],[15,18]]
//解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
// 
//
// 示例 2: 
//
// 输入: intervals = [[1,4],[4,5]]
//输出: [[1,5]]
//解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。 
//
// 注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。 
//
// 
//
// 提示： 
//
// 
// intervals[i][0] <= intervals[i][1] 
// 
// Related Topics 排序 数组 
// 👍 712 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

import java.util.Arrays;
import java.util.Comparator;

/**
 * Java：合并区间
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P56_MergeIntervals {
    public static void main(String[] args) {
        Solution solution = new P56_MergeIntervals().new Solution();
        int[][] array = {{1, 3}, {2, 6}, {8, 10}};
        MyUtil.printInt(array);
        int[][] merge = solution.merge(array);
        MyUtil.printInt(merge);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[][] merge(int[][] intervals) {
            if (intervals == null || intervals.length < 2) {
                return intervals;
            }
            // 按第一个元素升序排序
            Arrays.sort(intervals, (k1, k2) -> k1[0] - k2[0]);
            // 定义结果数组和位置，最长不超过intervals.length
            int idx = -1;
            int[][] res = new int[intervals.length][2];
            for (int[] arr : intervals) {
                // 当前是首位元素直接加进去
                // res最大值小于当前最小值则也直接加进去
                if (idx == -1 || res[idx][1] < arr[0]) {
                    res[++idx] = arr;
                }
                // 其他情况表示res最大值大于当前最小值，res最小值不变，最大值变成新的最大值
                else {
                    res[idx][1] = Math.max(res[idx][1], arr[1]);
                }
            }
            // 去掉null元素返回新数组
            return Arrays.copyOf(res, idx + 1);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}